Problems with Standard BP Decoders of LDPC Codes
Properly designed low-density parity-check (LDPC) codes, when decoded using belief propagation (BP) decoders, can achieve near Shannon limit performance in the so-called “water-fall” regime where the signal-to-noise ratio (SNR) is near the code threshold. Numerous BP decoders are known in the prior art. The U.S. Patent Database reveals over 500 hundred related patents and applications.
Prior art BP decoders are instances of message-passing methods that operate on a graphical representation known as a “factor graph,” see F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Factor Graphs and the Sum-Product Algorithm,” IEEE Transactions on Information Theory, vol. 47, pp. 498-519, 2001. BP decoders pass “messages” between “variable nodes” and “constraint nodes” in the factor graph, and update probabilities (“beliefs”) as to what a decoded codeword should be. Herein, “belief” is a term of art that is universally used to describe BP decoders. The major characteristics that distinguish different BP decoders are how messages and beliefs are iteratively updated.
Two versions of BP decoders are considered standard: the “min-sum” (or equivalent “max-product”) BP decoder and the “sum-product” BP decoder. The min-sum decoder is optimal in the sense that it always returns the most likely transmitted codeword, when the factor graph representing the code is a tree. Unfortunately, the factor graphs for good codes invariably contain cycles, and in the presence of cycles, the min-sum BP decoder becomes sub-optimal.
Sub-optimal sum-product BP decoders nevertheless achieve near Shannon limit performance for good graph-based codes in the waterfall regime, but unfortunately, the same is not true in the high-SNR regime. In the high-SNR regime graph-based codes paired with sum-product or min-sum BP decoders often suffer from an “error floor” phenomena, whereby the decoder error rate improves only slowly as the SNR increases. The error floor is a significant problem for applications that require extremely high reliability for high bit densities and data rates. It limits the applicability of current generation graph-based codes in such applications, which include magneto-optic data storage, and fiber-optic communications.
Error floors in graph-based codes using BP decoders are widely believed to result from structures in the code that go under the names “near-codewords,” “pseudo-codewords,” “instantons,” “absorbing sets,” and “trapping sets,” see T. Richardson, “Error Floors of LDPC Codes,” Proceedings of the 41st Allerton Conference on Communications, Control, and Computing, 2003. Error patterns resulting from channel transmission that strongly overlap these patterns are uncorrectable by the decoder.
Approaches to improve the error floor, while maintaining good water-fall behavior, can be categorized in two groups. One group constructs codes that have fewer trapping sets, and therefore improved error floors, when decoded using standard BP decoders. The number of the trapping sets, and therefore the error floor is improved by, e.g., constructing codes with fewer short cycles in the factor graph. One can also consider special classes of LDPC codes, such as EG-LDPC codes, or generalized LDPC codes that have fewer trapping sets. However, for many applications, specified codes, or codes of specified blocklengths and rates, may be required, and this approach may not be possible to implement because there may be no way to construct codes meeting the required specifications that also have good error floor behavior when decoded using standard BP decoders.
The other group of approaches to improving the error floor behavior, related to the present invention, improves the decoder. This approach is logical because random regular LDPC codes have (with high probability) excellent distance properties, and therefore, would not have error floors if the decoder used optimal maximum-likelihood (ML) decoding. (Note however that optimal decoders are normally too complex to be practical.)
For instance, if the trapping sets of a particular code are enumerated, a “bi-mode syndrome-erasure decoder” can improve the error floor behavior, see Y. Han and W. E. Ryan, “Low-floor decoders for LDPC Codes,” Proceedings of the 45th Annual Allerton Conference on Communications, Control, and Computing 2007, pp. 473-479. However, for many codes the enumeration of the trapping sets is itself an extremely challenging task.
Another improved decoder is the mixed-integer linear programming (MILP) decoder, which requires no information about trapping sets and approaches ML performance, but has a large decoding complexity. To deal with the complexity of the MILP decoder, a multistage decoder can be used, see Y. Wang, J. S. Yedidia, and S. C. Draper, “Multi-stage Decoding Via Mixed-Integer Adaptive Linear Programming,” Proceedings of the IEEE International Symposium on Information Theory, 2009, pp. 2151-2155. The multistage decoder combines fast but poor-performing decoders with more powerful, but slower MILP decoders so that one can obtain a decoder that performs as well as the MILP decoder and with a high average throughput. Nevertheless, the multistage decoder has considerable practical difficulties, in that it requires multiple decoders, and the worst-case throughput is as slow as the MILP decoder.
Therefore, it is desired to provide practical BP decoders for LDPC codes that have an improved error floor when compared with standard BP decoders, but with comparable complexity, and no significant disadvantages.
The Divide and Concur Constraint Optimization Method
Our invention, described below, is motivated in part by a method described by Gravel and Elser, “Divide and Concur: a General Approach to Constraint Satisfaction,” Phys. Rev. E 78, 036706, 2008, hereinafter D&C.
The motivation of Gravel and Elser was to solve complex computational problems, such as the problem of reconstructing the shapes of macromolecules in x-ray crystallography. Other applications investigated using the D&C method relate to protein folding, finding ground states of spin glasses, satisfiability testing, protein structure prediction, Ramsey numbers, solving diophantine equations, and even solving Sudoku puzzles. Many of those applications are NP-complete problems. Another of their motivations was to find improved solutions to some old and well-studied optimization problems, such as sphere packing.
The D&C method is a solution technique for constraint satisfaction problems that have N variables and M constraints. Each constraint involves a subset of the N variables. The objective is to determine a configuration of the N variables such that all M constraints are satisfied. Instead of working directly with variable values, the D&C method instead is concerned with the dynamics of “replicas” of the variables. For each variable involved in a particular constraint, a replica of that variable is generated. The number of replicas of a particular variable equals the number of constraints that variable is involved in.
D&C uses “divide projections” and “concur projections.” During a divide projection, replica values are modified, by as small a change as possible, such that each constraint is locally satisfied. During a concur projection, (possibly different) replicas of the same variable are forced to equal each other by averaging their values.
A key idea in the D&C algorithm is to avoid “short cycles” (or “traps”) in the dynamics through the use of a “difference map” (DM) combination of “divide” and “concur” projections at each iteration.
Let r be the vector containing all the values of replicas of all variables. This vector can be partitioned into mutually exclusive sets in two distinct ways. First, it can be partitioned into sets of replicas corresponding to each constraint. We use r(a) to denote the vector of replica values of all the replicas associated with a constraint a, where a can take on integer values between 1 and M. Second, it can be partitioned into a set of replicas corresponding to each variable. We use r[i] to denote the vector of replica values of all replicas associated with a variable i, where i can take on integer values between 1 and N.
The “divide projection” PD forces all constraints to be satisfied, by changing the replica values r(a) as little as possible, and is applied independently to each set r(a) for a from 1 to M. After application of the divide projection, replicas of the same variable do not necessarily agree with one another.
The “concur projection” PC equalizes the replicas of the same variable and is applied independently to each set r[i] for i from 1 to N. After application of the concur projection, replicas of the same variable agree with one another but the constraints are not necessarily all satisfied.
A strategy is needed to combine the two projections to find a set of replica values that satisfy all constraints, and at the same time ensure that all replicas associated with each variable are equal. Perhaps the most obvious way to use the formalism of replicas and the divide and concur projections is a straightforward alternation between the two projections. This “alternating projections” approach works well for convex constraints, but otherwise sometimes gets “stuck” in short cycles that do not correspond to correct solutions.
FIG. 1 illustrates an example where the alternating projections approach fails. In the figure, there are only two replicas represented by the x- and y-values. The diagonal line represents the requirement that replica values are equal, while the points A and B correspond to the two pairs of replica values that satisfy the other constraints. The only solution that satisfies the constraints and the requirement that the replicas are equal is at point A. Say that the replica values are initialized to those corresponding to point D. If one applies alternating projections, the starting point D is first projected to the nearest pair of values that satisfies the constraints. This is point B. Application of the concur projection bring the next update to the nearest pair of replica values along the solid line, i.e., point C. Henceforth, alternating projection causes the pair of replica values to be stuck in the short cycle (BC), and the true solution at A is never found.
The difference map (DM) dynamics improves upon the alternating projections strategy by modifying the combination of the divide and concur projections in a way that turns short cycles into “repellers.” The dynamics of the DM for a single iteration is a three step process.                In the first step, the replicas move twice the desired amount indicated by the divide projection. Their new values are now called “overshoot” values of the replicas.        In the second step, the concur projection is applied to the overshoot values of the replicas to obtain “concurred” values of the replicas.        In the third step, the concurred values of the replicas are corrected to obtain the replica for the next iteration by subtracting the amount that the replicas values were “overshot” in the first step.        
The dynamics of the DM are illustrated in FIG. 2. The scenario depicted in the figure is the same as in FIG. 1. Thus, if one were to initialize replica values at r1 and apply alternating projections, then the dynamics get stuck in the cycle between B and r1. The figure instead illustrates what happens if the replicas are initialized to r1 but the DM is applied. The DM dynamics repels one from the cycle and moves to r2, (via the three steps denoted with dashed lines r1over, r1conc=r1 and r2), and then moves to r3, and ends at r4=r*, which corresponds to the solution at A. The sequence of calculations and updated values for this example are tabulated in Table I, below.
TABLE ItrtPD(rt)rtoverrtconc1(2, 2)(3, 1)(4, 0)  (2, 2)2(1, 3)(3, 1)(5, −1)(2, 2)3(0, 4)(0, 0)(0, −4)(−2, −2)4(−2, 2)  (0, 0)(2, −2)(0, 0)5(−2, 2)  
Of course, DM might get caught in more complicated cycles or “strange attractors” and never find an existing solution; but least it does not get caught in simple local cycles.